System testing contributes significantly to system development and maintenance costs. TestMaster® software sold by Teradyne® Software and System Test, Inc. of Nashua, N.H. can reduce testing costs while increasing testing quality.
Referring to FIG. 1, TestMaster® software 100 enables a designer to create 102 an extended finite state machine model of a system. An extended finite state machine is represented by a directed graph that includes states interconnected by transitions. The software 100 provides a graphical user interface that enables the designer to “draw” the model by defining the states and connecting them together with directional lines that represent transitions. The model is independent of the system being modeled and can be created before or after the system is developed.
After the designer creates 102 the model, the software 100 detects 104 paths through the model states and transitions and generates 106 testing programs corresponding to each of the detected paths. Execution of the generated testing programs can identify system design flaws and highlight differences between the model created and the actual behavior of the underlying system.
Referring to FIG. 2, an extended finite state machine model 108 of a system includes states 110-116 interconnected by transitions 118-124. For example, as shown, a model 108 includes states 110-116 and transitions 118-124 representing a bank machine system that dispenses cash to customers entering an authorized PIN (Personal Identification Number).
The TestMaster® system automatically detects different paths through the model 108. For example, as shown in FIG. 3, a path through the model can include model elements A-TAB-B-TBC-C-TCD-D. This path corresponds to a customer correctly entering an authorized PIN and successfully withdrawing cash. As shown in FIG. 4, a different path through the model can include model elements A-TAB-B-TBD-D. This model path corresponds to a customer who fails to correctly enter an authorized PIN.
TestMaster® offers many different procedures for detecting paths through a model. For example, a user can select from comprehensive, transition-based, N-switch, and quick-cover path detection. Comprehensive path detection outputs a test for every possible path through the model. Transition based path detection outputs tests such that each transition is included in at least one test. N-switch path detection outputs tests such that each unique sequence of N+1 transitions are included in at least one test. Comprehensive, transition, and N-switch path detection are currently implemented using a depth-first search. In contrast, quick-cover uses a “top-down” search and can output tests such that no transition is used more than a specified number of times. U.S. Pat. No. 08/658,344 entitled “Method and Apparatus for Adaptive Coverage in Test Generation” describes implementations of programs for detecting extended finite state machine paths.
Referring again to FIG. 2, in addition to transitions and states, a model can incorporate variables and expressions that further define the model's behavior. TestMaster® can evaluate the expressions to assign variable values (e.g., y=mx+b) or to determine whether an expression is TRUE or FALSE (e.g., A AND (B OR C)). The expressions can include operators, variables, and other elements such as the names of states, transitions, and/or sub-models. When a named state, transition, or sub-model is in included in an expression, the model element evaluates to TRUE when included in the path currently being detected. For example, in FIG. 2, an expression of “(A && B)” would evaluate to TRUE for path portion “A-TB-B”. As shown, expressions can use a PFL (Path Flow Language) syntax that resembles the C programming language. PFL and functions that can be called from PFL are described in The TestMaster® Reference Guide published by Teradyne®.
A model designer can associate the expressions with model elements to further define model behavior. For example, a designer can associate predicates and/or constraints with different states, transitions, and/or submodels. Both predicates and constraints are evaluated during path detection and determine which transitions can be included in a path.
When path detection instructions encounter a model element having an associated predicate, the predicate expression is evaluated. If the predicate evaluates to TRUE, the model element associated with the predicate can be used in the path. For example, as shown in FIG. 2, transition TBD 124 has an associated predicate 126 (“!OKPin”) that determines when a path can include the transition. As shown, the predicate 126 is a boolean expression that permits inclusion of the transition 124 in a path being detected when the boolean variable OKPin is FALSE and the path being detected has reached state B.
Similarly, when path detection instructions encounter a model element having an associated constraint, the constraint expression is evaluated. If the constraint evaluates to FALSE, the model element associated with the constraint cannot be used in the path being detected. For example, as shown in FIG. 2, a transition 123 can connect a state 114 to itself. To prevent a path from including a large or possibly infinite number of the same transition in a single path, a designer can specify a constraint expression 125 that limits use of a transition in a path. The “Iterate(3)” expression associated with the transition 123 limits a path through the model to including transition 123 three times. Thus, if evaluated at state C after looping around transition TCC three times, the constraint would evaluate to FALSE and prevent further use of the transition in the current path. The constraint acts as a filter, eliminating generation of unwanted testing programs.
Referring to FIG. 5, a model can also include one or more sub-models. For example, the box labeled “EnterPIN” in FIG. 2 may be a sub-model 112 that includes additional states 128-136, transitions 138-150, and expressions. As shown, the sub-model 112 sets 150 the model variable OKPin to TRUE when the customer PIN equals 1 148; otherwise, the sub-model sets the model variable OKPin to FALSE 146.
Sub-models encourage modular system design and increase comprehension of a model's design. Referring to FIG. 6, when the software 100 detects different paths through the system, the sub-model is essentially replaced with the states and transitions included in the sub-model.
Referring again to FIG. 5, a designer can define more than one transition 138-142 between states 128, 130. The designer can also associate expressions (e.g., PIN=1) with each transition 138-142, for example, to set model variables to different values. For example, as shown, a designer has defined three transitions between the “Entry” 128 and “PINEntry” 130 states that each set a PIN variable to different value. Defining multiple transitions between states increases the number of paths through a model. For example, paths through the sub-model 112 can include I-TIJ(1)-J-TJK-K-TKM-M, I-TIJ(2)-J-TJL-L-TLM-M, and I-TIJ(3)-J-TJL-L-TLM-M. The use of multiple transitions enables testing of different conditions within the same model.